//给你一个整数数组 nums 。你可以选定任意的 正数 startValue 作为初始值。 
//
// 你需要从左到右遍历 nums 数组，并将 startValue 依次累加上 nums 数组中的值。 
//
// 请你在确保累加和始终大于等于 1 的前提下，选出一个最小的 正数 作为 startValue 。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [-3,2,-3,4,2]
//输出：5
//解释：如果你选择 startValue = 4，在第三次累加时，和小于 1 。
//                累加求和
//                startValue = 4 | startValue = 5 | nums
//                  (4 -3 ) = 1  | (5 -3 ) = 2    |  -3
//                  (1 +2 ) = 3  | (2 +2 ) = 4    |   2
//                  (3 -3 ) = 0  | (4 -3 ) = 1    |  -3
//                  (0 +4 ) = 4  | (1 +4 ) = 5    |   4
//                  (4 +2 ) = 6  | (5 +2 ) = 7    |   2
// 
//
// 示例 2： 
//
// 
//输入：nums = [1,2]
//输出：1
//解释：最小的 startValue 需要是正数。
// 
//
// 示例 3： 
//
// 
//输入：nums = [1,-2,-3]
//输出：5
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 100 
// -100 <= nums[i] <= 100 
// 
// Related Topics数组 | 前缀和 
//
// 👍 51, 👎 0 
//
//
//
//

package leetcode.editor.cn;

class MinimumValueToGetPositiveStepByStepSum {
    public static void main(String[] args) {
        Solution solution = new MinimumValueToGetPositiveStepByStepSum().new Solution();
        solution.minStartValue(new int[]{-3, 2, -3, 4, 2});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /*public int minStartValue(int[] nums) {
            int n = nums.length;
            for (int i = 1; i < Integer.MAX_VALUE; i++) {
                int sum = 0;
                boolean flag = true;
                for (int j = 0; j < n; j++) {
                    if (j == 0) sum = i + nums[j];
                    else sum += nums[j];

                    if (sum < 1) {
                        flag = false;
                        break;
                    }
                }

                if (flag) return i;
            }

            return 1;
        }*/

        // 贪心，找前缀和最小的加一
        // sum + startValue = 1，只需要保证累加和最小的sunMin + startValue = 1，相当于前缀和
        /*public int minStartValue(int[] nums) {
            int sum = 0, sumMin = 0;
            for (int num : nums) {
                sum += num;
                sumMin = Math.min(sum, sumMin);
            }

            return -sumMin + 1;
        }*/

        // 二分
        // 某个数字满足startValue的要求时，比他大的数字肯定都满足，比他小的数字不一定满足,因此startValue具有单调性
        // https://leetcode.cn/problems/minimum-value-to-get-positive-step-by-step-sum/solution/zhu-bu-qiu-he-de-dao-zheng-shu-de-zui-xi-vyrt/
        public int minStartValue(int[] nums) {
            int min = Integer.MAX_VALUE;
            for (int num : nums) {
                min = Math.min(min, num);
            }

            if (min >= 0) return 1;

            // 左边界为1，右边界所有数默认为最小值 + 1进行搜索
            int l = 1, r = -min * nums.length + 1;
            while (l < r) {
                int m = l + (r - l) / 2;
                if (!f(m, nums)) {
                    // false，左边界扩大
                    l = m + 1;
                } else {
                    // true，右缩小
                    r = m;
                }
            }

            return l;
        }

        public boolean f(int startValue, int[] nums) {
            for (int num : nums) {
                startValue += num;
                if (startValue < 1) {
                    return false;
                }
            }

            return true;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)
}
